package algorithm.horsechess;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * 马踏棋盘算法 回溯思想 + 贪心算法
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-08
 */
public class HorseRidingChessBoard {

    /**
     * 棋盘的列
     */
    private static int X;

    /**
     * 棋盘的行
     */
    private static int Y;

    /**
     * 是否被访问
     */
    private static boolean[] isVisited;

    /**
     * 是否完成马踏棋盘
     */
    private static boolean finished = false;

    public static void main(String[] args) {
        System.out.println("开始马踏棋盘~~~~");
        X = 8;
        Y = 8;
        isVisited = new boolean[X * Y];
        int[][] chess = new int[Y][X];
        int row = 1;
        int col = 1;
        long start = System.currentTimeMillis();
        traversalChessboard(chess, row - 1, col - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));

    }

    /**
     * 马踏棋盘算法
     *
     * @param chess 棋盘
     * @param row   行
     * @param col   列
     * @param step  当前第几步
     */
    public static void traversalChessboard(int[][] chess, int row, int col, int step) {
        chess[row][col] = step;
        // 标记该位置已访问
        isVisited[row * X + col] = true;
        // Point x 表示列 y 表示行
        ArrayList<Point> points = nextList(new Point(col, row));
        // 这里体现贪心算法 对下一个point对象的下一步位置的数目排序 减少回溯次数
        sort(points);
        while (!points.isEmpty()) {
            Point point = points.remove(0);
            if (!isVisited[point.y * X + point.x]) {
                // 说明还没访问
                traversalChessboard(chess, point.y, point.x, step + 1);
            }
        }

        if (step < X * Y && !finished) {
            // 如果还没走完
            chess[row][col] = 0;
            isVisited[row * X + col] = false;
        } else {
            finished = true;
        }

    }

    /**
     * 对ps进行排序，排序规则就是对ps的所有point对象的下一步位置的数目，进行非递减排序
     * @param ps
     */
    private static void sort(ArrayList<Point> ps) {
        ps.sort(Comparator.comparingInt(o -> nextList(o).size()));

    }

    public static ArrayList<Point> nextList(Point curPoint) {

        ArrayList<Point> ps = new ArrayList<>(8);
        Point p1 = new Point();

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }

        return ps;
    }
}

